분할 정복 알고리즘
2020-10-15
분할 정복 알고리즘
분할 정복 알고리즘은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다. 대표적으로는 퀵소트 나 병합정렬이 있다.
그림에서와 같이 분할 정복법은 상단에서 분할하고 중앙에서 정복하고 하단에서 조합(Combine)하는 형태로 도식화 할 수 있다.
- 분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다.
- 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.
- 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.
분할 정복 알고리즘은 보통 재귀 함수를 통해 자연스럽게 구현된다. 하지만 이러한 재귀 호출을 사용한 함수는 함수 호출 오버헤드 때문에 실행 속도가 늦어진다.
빠른 실행이나 분할된 문제 해결 순서 선택을 위해 재귀호출을 사용하지 않고 스택, 큐 등의 자료구조를 이용하여 분할 정복법을 구현하는 것도 가능하다.